<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.1">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/dute_favicon_32x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/dute_favicon_16x16.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">
  <link rel="manifest" href="/images/manifest.json">
  <meta name="msapplication-config" content="/images/browserconfig.xml">
  <meta http-equiv="Cache-Control" content="no-transform">
  <meta http-equiv="Cache-Control" content="no-siteapp">
  <meta name="google-site-verification" content="mpI5dkydstZXl6UcDCppqktXK0bbvqdZ6LkZ3KNk4Iw">
  <meta name="baidu-site-verification" content="code-a1LksZX2Ds">

<link rel="stylesheet" href="/css/main.css">


<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/gh/fancyapps/fancybox@3/dist/jquery.fancybox.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"whitestore.top","root":"/","scheme":"Gemini","version":"7.8.0","exturl":true,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":true,"scrollpercent":true},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":true,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="Skiplist跳表">
<meta property="og:type" content="article">
<meta property="og:title" content="LSM-Tree - LevelDb Skiplist跳表">
<meta property="og:url" content="https://whitestore.top/2022/05/21/level-skiplist/index.html">
<meta property="og:site_name" content="爱看书的阿东">
<meta property="og:description" content="Skiplist跳表">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/20220519072104.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/20220519075430.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/20220519073220.png">
<meta property="og:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/20220519075520.png">
<meta property="article:published_time" content="2022-05-21T11:10:02.000Z">
<meta property="article:modified_time" content="2023-07-16T06:28:09.225Z">
<meta property="article:author" content="阿东">
<meta property="article:tag" content="Skiplist跳表">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/20220519072104.png">

<link rel="canonical" href="https://whitestore.top/2022/05/21/level-skiplist/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>LSM-Tree - LevelDb Skiplist跳表 | 爱看书的阿东</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

<link rel="alternate" href="/atom.xml" title="爱看书的阿东" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">爱看书的阿东</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">赐他一块白色石头，石头上写着新名</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-fw fa-home"></i>首页</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-fw fa-tags"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="fa fa-fw fa-th"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-fw fa-archive"></i>归档</a>

  </li>
        <li class="menu-item menu-item-sitemap">

    <a href="/sitemap.xml" rel="section"><i class="fa fa-fw fa-sitemap"></i>站点地图</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    

  <span class="exturl github-corner" data-url="aHR0cHM6Ly9naXRodWIuY29tL2xhenlUaW1lcw==" title="Follow me on GitHub" aria-label="Follow me on GitHub"><svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></span>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://whitestore.top/2022/05/21/level-skiplist/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="阿东">
      <meta itemprop="description" content="随遇而安">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="爱看书的阿东">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          LSM-Tree - LevelDb Skiplist跳表
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2022-05-21 19:10:02" itemprop="dateCreated datePublished" datetime="2022-05-21T19:10:02+08:00">2022-05-21</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2023-07-16 14:28:09" itemprop="dateModified" datetime="2023-07-16T14:28:09+08:00">2023-07-16</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/LevelDB/" itemprop="url" rel="index"><span itemprop="name">LevelDB</span></a>
                </span>
            </span>

          
            <span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv" style="display: none;">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">阅读次数：</span>
              <span id="busuanzi_value_page_pv"></span>
            </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2022/05/21/level-skiplist/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2022/05/21/level-skiplist/" itemprop="commentCount"></span>
    </a>
  </span>
  
  <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="fa fa-file-word-o"></i>
              </span>
                <span class="post-meta-item-text">本文字数：</span>
              <span>8.2k</span>
            </span>
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="fa fa-clock-o"></i>
              </span>
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              <span>7 分钟</span>
            </span>
            <div class="post-description">Skiplist跳表</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="LSM-Tree-LevelDb-Skiplist跳表"><a href="#LSM-Tree-LevelDb-Skiplist跳表" class="headerlink" title="LSM-Tree - LevelDb Skiplist跳表"></a>LSM-Tree - LevelDb Skiplist跳表</h1><h1 id="跳表介绍"><a href="#跳表介绍" class="headerlink" title="跳表介绍"></a>跳表介绍</h1><p>跳表（SkipList）是由William Pugh提出的。他在论文<Skip lists: a probabilistic alternative to balanced trees>中详细地介绍了有关跳表结构、插入删除操作的细节。</p>
<blockquote>
<p>文档：Skiplist跳表原始论文 - pugh-skiplists-cacm1990.pdf<br>链接：<span class="exturl" data-url="aHR0cDovL25vdGUueW91ZGFvLmNvbS9ub3Rlc2hhcmU/aWQ9NjY3YWVkOTZmMDEyZWRjYWRhMDQ3YmFmNzVhYTE3NjkmYW1wO3N1Yj1CNDI3RTAwQzgxOEI0MjhBQkQzOEE4MTMxODBBRjlBOA==" title="http://note.youdao.com/noteshare?id=667aed96f012edcada047baf75aa1769&amp;sub=B427E00C818B428ABD38A813180AF9A8">http://note.youdao.com/noteshare?id=667aed96f012edcada047baf75aa1769&amp;sub=B427E00C818B428ABD38A813180AF9A8<i class="fa fa-external-link"></i></span></p>
</blockquote>
<h2 id="背景"><a href="#背景" class="headerlink" title="背景"></a>背景</h2><p>在线性的数据数据结构中我们经常可以想到数组和链表，数组是插入慢查询快，而链表是插入快，查询要稍微慢一些，而跳表主要是针对链表<strong>查询速度</strong>进行优化的一种数据结构，多层级的跳表实际上是对底层链表的索引，非常典型的空间换时间，把链表的查询时间尽量控制在O(logN)。</p>
<a id="more"></a>

<h2 id="实现"><a href="#实现" class="headerlink" title="实现"></a>实现</h2><p>由于使用了类似索引点数据维护方式，所以新增和删除需要同时维护跳表结构，跳表利用概率平衡的方式简化新增和删除操作，和树操作利用左旋和右旋等操作维持数据平衡不同，跳表利用了类似猜硬币的方式抉择出在哪一层插入或者删除节点和更新索引。</p>
<p>从下面的abcde图中，我们可以看一下跳表的演进：</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/20220519072104.png" alt=""></p>
<p>首先a是一个典型的链表结构，对于查询来说需要<code>O(n)</code>的时间，链表长度越长查询越慢。</p>
<p>b在a的基础上，每次隔2个节点加一个额外的指针，通过这样的操作，每次查询时间就减少了【n/2】+次数。</p>
<p>c、d、e继续按照这样的思路继续加额外指针，最终只留下从头到尾的一层指针结束。</p>
<p>但是可以看到如果按照统一的思路每一层这样加节点对于维护整个节点的效率十分低，我们将拥有额外指针的节点看作一个K层节点，按照图中整理可以看到对于1层的节点占了50%，2层为25%，3层为12.5%……如果插入新节点能按照这样的规律进行插入删除，那么效率提升就不会出现很大的性能影响。</p>
<p>维护辅助指针会带来更大的复杂度，索引在每一层的节点中都会指向当前层所在的下一个节点，也就是说每一层都是一个链表。</p>
<p><strong>时间复杂度如何计算的？</strong></p>
<p>推导公式如下：</p>
<p><code>n/2^k =&gt; n / 2^k = 2 =&gt; h = log2n -1 =&gt; O(logn)</code></p>
<p>k代表节点层数，h表示最高级</p>
<p>原始的链表有n个元素，则一级索引有n/2 个元素、二级索引有 n/4 个元素、k级索引就有 n/(2^k)个元素。最高级索引一般有2个元素（头指向尾），最高级索引指向2 = n/(2^h)，即 h =(log2)n-1，最高级的索引h为索引层高度+原数据高度，最终跳表高度为 h = (log2) n。</p>
<p>经过索引的优化之后，整个查询的时间复杂度可以近似看作<strong>O(logn)</strong> ，和 二分查找的效率类似。</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/20220519075430.png" alt=""></p>
<p><strong>空间复杂度如何计算？</strong></p>
<p>随着层数的增加，建立索引的空间开销是越来越小的，一层索引为 n/2，二层索引为 n/4，三层为 n/8 …..最后 n/2 + n/4 + n/8 +…. + 2（最高层一般为2个节点）最后因为分母相加可以认为是近似 <strong>O(n)</strong> 的空间复杂度。</p>
<h2 id="查询"><a href="#查询" class="headerlink" title="查询"></a>查询</h2><p>下面是跳表的增删改查的处理流程，由于删除和插入都依赖查询，我们先从查询开始介绍：</p>
<p>查询的操作方式可以看下面的绘图，比如如果需要查找存在于中间的节点17，则会根据线条顺序查找，这里简述查询顺序：</p>
<ol>
<li>从索引的最高层进行查找，直接找到下一个节点。</li>
<li>如果当前内容大于节点内容，则直接找下一个节点比较。</li>
<li>如果当前节点等于查找节点则直接返回。</li>
<li>如果当前节点大于节点，并且下一个节点大于当前节点，并且层高不为0，则继续往层高更低的一个层级节点查找同时<strong>回到更低层级前一个节点</strong>，如果层高为0，则返回当前节点，当前节点的key要大于查找的key。</li>
</ol>
<p>查找比较好理解，就是用索引快速跨越多个链表节点减少搜索次数，然后层数下探找到相关的节点，注意拥有索引的节点，通常在上层节点会有指向下层的指针。</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/20220519073220.png" alt=""></p>
<h2 id="插入"><a href="#插入" class="headerlink" title="插入"></a>插入</h2><p>插入操作比较关键，因为这里涉及到非常影响跳表性能的索引节点选举动作。按照之前的查找操作步骤，插入操作需要<strong>每次记录每一层的前任节点</strong>。</p>
<p><strong>关键点</strong>：插入的关键点在于选举那个节点增加层高来维持二分查找的效率，在找到位置之后，通常使用随机抛硬币的方式随机为节点增加层高，层级越高被选中的概率通常会指数倍的降低，之后根据三个参数：种子（用于实现概率随机）以及当前节点的层数和概率值P或者其他的随机值算法进行计算，但是为了防止单节点层高过高，通常会限制最终层高防止单一节点的层高超过上限。</p>
<blockquote>
<p>根据墨菲定律，无论单一节点层高过高可能性再低，都需要做限制。</p>
</blockquote>
<p>这里挑了LevelDB跳表数据结构的一段代码进行介绍：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">func (p *DB) randHeight() (h <span class="keyword">int</span>) &#123;</span><br><span class="line">	<span class="comment">// 限制跳表扩展的最高层级</span></span><br><span class="line">    <span class="keyword">const</span> branching = <span class="number">4</span></span><br><span class="line">    h = <span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> h &lt; tMaxHeight &amp;&amp; p.rnd.Int()%branching == <span class="number">0</span> &#123;</span><br><span class="line">        h++</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>插入节点之后，会根据记录的前任节点在每一层的位置按照跳表规则建立新节点的索引。</p>
<p>跳表插入新节点本身的更新十分非常简单，只需要把<strong>当前节点下一个节点指向插入节点的下一个节点的下一个节点，插入节点的下一个节点指向当前节点</strong> 即可。</p>
<p><img src="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/20220519075520.png" alt=""></p>
<p><strong>插入操作时间复杂度</strong></p>
<p>如果是单链表，那么一次遍历就可以完成，结果永远都是<strong>O(1)</strong>，对于跳表的插入，最坏的情况也就是需要在所有层都更新索引，这种情况是<strong>O(logN)</strong>。</p>
<h2 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h2><p>删除也是依赖查询完成的，根据查询找到待删除节点之后在每一层按照查询的规则把当前节点删除即可。</p>
<p>删除的时间复杂度快慢取决于于查询的层数，假设需要删除N个元素，而每一层其实都是一个单向的链表，单链表的查询是O(1)，同时是因为跳表最优是近似二分查找的效率，索引层数为logn，删除的层数也是logN，N取决于层级。</p>
<p>最终删除元素的总时间包含：</p>
<p>查找元素的时间 + _删除 logn个元素的时间 = <code>O(logn) + O(logn) = 2O(logn)</code>，忽略常数部分最终结果为 O(logn)。</p>
<h2 id="使用场景"><a href="#使用场景" class="headerlink" title="使用场景"></a>使用场景</h2><p>其实多数和Key-Value有关的LST-Tree 数据结构都有类似的跳表实现，因为链表在业务方面使用可能比较少，但是在数据结构和数据库设计上面却是至关重要的地位：</p>
<ul>
<li>HBase</li>
<li>Redis</li>
<li>LevelDB</li>
</ul>
<p><strong>小结</strong></p>
<ul>
<li>跳表让链表也能够完成二分查找的操作</li>
<li>元素的插入会根据抛硬币和权重分配随机选举Level</li>
<li>最底层永远是原始链表，而上层则是索引数据</li>
<li>索引节点通常会多一个指针指向下层节点，但是不是所有的程序设计都是按照这种方式，有其他的处理方式间接实现此功能（具体可以看redis 的 zset源代码）</li>
<li>跳表查询、插入、删除的时间复杂度为O(log n)，与平衡二叉树接近</li>
</ul>
<h1 id="LevelDb跳表实现"><a href="#LevelDb跳表实现" class="headerlink" title="LevelDb跳表实现"></a>LevelDb跳表实现</h1><p>在之前讨论合并压缩文件使用了归并排序的方式进行键合并，而内部的数据库除了归并排序之外还使用了比较关键的[[LSM-Tree - LevelDb Skiplist跳表]]来进行有序键值管理。</p>
<p>跳表在Redis和Kafka中都有实现，这里的Skiplist其实也是类似的，可以看作C++版本的跳表案例。</p>
<p>这部分就不看作者的文档了，我们直接源码开干。</p>
<h2 id="基础结构"><a href="#基础结构" class="headerlink" title="基础结构"></a>基础结构</h2><p>首先我们需要清楚LevelDB的跳表包含了什么东西？在代码的一开始定义了 <strong>Node</strong>节点用来表示链表节点，以及 <strong>Iterator</strong>迭代器的内容进行迭代，内部定义了<code>std::atomic&lt;Node*&gt; next_[1]</code> 长度等于节点高度的数组。 </p>
<p>next_[0]是最底层的节点（用于跳表跨层获取数据），核心是作者自认为写的一般的Random 随机器（通过位操作生成随机的一个位号码）。</p>
<p>LevelDB的整个实现比较简洁规范，在设计上定义了很多函数来简化复杂代码的增加，建议看不懂就多看几遍跳表的理论。</p>
<h2 id="重要方法"><a href="#重要方法" class="headerlink" title="重要方法"></a>重要方法</h2><p>#levelDB插入操作 #levelDB查询操作</p>
<p>在了解过[[LSM-Tree - LevelDb Skiplist跳表]]之后，我们发现对于跳表这种数据结构来说，核心部分在于查询和插入两个部分，当然查询是理解插入点前提，但是对于插入抛硬币选举的实现有必要深究一下。</p>
<h2 id="查询操作"><a href="#查询操作" class="headerlink" title="查询操作"></a>查询操作</h2><p>查询操作比较好理解，和跳表的数据结构规定差不多，和[[LSM-Tree - LevelDb Skiplist跳表]]的实现类似：</p>
<p>可以发现和跳表原始的实现方式如出一辙，这里相当于复读理论的内容：</p>
<ol>
<li>从索引的最高层进行查找，直接找到下一个节点。</li>
<li>如果当前内容大于节点内容，则直接找下一个节点比较。</li>
<li>如果当前节点等于查找节点则直接返回。</li>
<li>如果当前节点大于节点，并且下一个节点大于当前节点，并且层高不为0，则继续往层高更低的一个层级节点查找同时<strong>回到更低层级前一个节点</strong>，如果层高为0，则返回当前节点，当前节点的key要大于查找的key。</li>
</ol>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 返回层级最前的节点，该节点位于键的位置或之后。如果没有这样的节点，返回nullptr。如果prev不是空的，则在[0...max_height_1]中的每一级，将prev[level]的指针填充到前一个 节点的指针来填充[0...max_height_1]中的每一级的 "level"。</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> Key, <span class="class"><span class="keyword">class</span> <span class="title">Comparator</span>&gt;</span></span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="title">typename</span> <span class="title">SkipList</span>&lt;Key, Comparator&gt;:</span>:Node*</span><br><span class="line"></span><br><span class="line">SkipList&lt;Key, Comparator&gt;::FindGreaterOrEqual(<span class="keyword">const</span> Key&amp; key,</span><br><span class="line"></span><br><span class="line">Node** prev) <span class="keyword">const</span> &#123;</span><br><span class="line"></span><br><span class="line">	Node* x = head_;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 防止无限for循环</span></span><br><span class="line">	<span class="keyword">int</span> level = GetMaxHeight() - <span class="number">1</span>;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">while</span> (<span class="literal">true</span>) &#123;</span><br><span class="line">	</span><br><span class="line">		Node* next = x-&gt;Next(level);</span><br><span class="line">		</span><br><span class="line"></span><br><span class="line">		<span class="keyword">if</span> (KeyIsAfterNode(key, next)) &#123;</span><br><span class="line">			</span><br><span class="line">			<span class="comment">// 如果当前节点在层级之后，则查找下一个链表节点</span></span><br><span class="line">			</span><br><span class="line">			x = next;</span><br><span class="line">		</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			</span><br><span class="line">		</span><br><span class="line">			<span class="keyword">if</span> (prev != <span class="literal">nullptr</span>) prev[level] = x;</span><br><span class="line">			</span><br><span class="line">			<span class="keyword">if</span> (level == <span class="number">0</span>) &#123;</span><br><span class="line">			</span><br><span class="line">				<span class="keyword">return</span> next;</span><br><span class="line">		</span><br><span class="line">			&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			</span><br><span class="line">				<span class="comment">// 层级下沉</span></span><br><span class="line">				</span><br><span class="line">				level--;</span><br><span class="line">			</span><br><span class="line">			&#125;</span><br><span class="line">	</span><br><span class="line">		&#125;</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="插入操作"><a href="#插入操作" class="headerlink" title="插入操作"></a>插入操作</h2><p>插入操作的代码如下，注意跳表需要在插入之前对于节点进行加锁的操作。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> Key, <span class="class"><span class="keyword">class</span> <span class="title">Comparator</span>&gt;</span></span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="title">void</span> <span class="title">SkipList</span>&lt;Key, Comparator&gt;:</span>:Insert(<span class="keyword">const</span> Key&amp; key) &#123;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 因为前置节点最多有kMaxHeight层，所以直接使用kMaxHeight 简单粗暴</span></span><br><span class="line">	Node* prev[kMaxHeight];</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 返回层级最前的节点，该节点位于键的位置或之后。如果没有这样的节点，返回nullptr。如果prev不是空的，则在[0...max_height_1]中的每一级，将prev[level]的指针填充到前一个 节点的指针来填充[0...max_height_1]中的每一级的 "level"。</span></span><br><span class="line">	Node* x = FindGreaterOrEqual(key, prev);</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 不允许进行重复插入操作（同步加锁）</span></span><br><span class="line">	assert(x == <span class="literal">nullptr</span> || !Equal(key, x-&gt;key));</span><br><span class="line">	</span><br><span class="line">	<span class="comment">// **新增层级选举**，使用随机函数和最高层级限制，按照类似抛硬币的规则选择是否新增层级。</span></span><br><span class="line">	<span class="comment">// 随机获取一个 level 值</span></span><br><span class="line">	<span class="keyword">int</span> height = RandomHeight();</span><br><span class="line">	</span><br><span class="line">	<span class="comment">// 当前随机level是否大于 当前点跳表层数</span></span><br><span class="line">	<span class="keyword">if</span> (height &gt; GetMaxHeight()) &#123;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 头指针下探到最低层</span></span><br><span class="line">	</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = GetMaxHeight(); i &lt; height; i++) &#123;</span><br><span class="line">			prev[i] = head_;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">/*</span></span><br><span class="line"><span class="comment">		这部分建议多读读原注释。</span></span><br><span class="line"><span class="comment">		</span></span><br><span class="line"><span class="comment">		机器翻译：在没有任何同步的情况下突变max_height_是可以的。与并发读取器之间没有任何同步。一个并发的读者在观察到的新值的并发读者将看到max_height_的旧值。的新水平指针（nullptr），或者在下面的循环中设置一个新的值。下面的循环中设置的新值。在前一种情况下，读者将立即下降到下一个级别，因为nullptr会在所有的键之后。在后一种情况下，读取器将使用新的节点</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">		理解：意思是说这一步不需要并发加锁，这是因为并发读读取到更新的跳表层数，哪怕现在这个节点没有插入，也会返回nullptr，在leveldb的比较器当中的nullpt会在最前面，默认看作比所有的key都要大，所以会往下继续找，这样就可以保证写入和读取都是符合预期的。</span></span><br><span class="line"><span class="comment">		*/</span></span><br><span class="line">		max_height_.store(height, <span class="built_in">std</span>::memory_order_relaxed);</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">// 新增跳表节点</span></span><br><span class="line">	x = NewNode(key, height);</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; height; i++) &#123;</span><br><span class="line">	<span class="comment">// NoBarrier_SetNext()就够了，因为当我们在prev[i]中发布一个指针 "x "时，我们会添加一个障碍。我们在prev[i]中发布一个指向 "x "的指针。</span></span><br><span class="line">    </span><br><span class="line">		<span class="comment">// 更新指针引用</span></span><br><span class="line">		<span class="comment">// 为了保证并发读的准确性，需要先设置节点指针然后再设置原始表的prev 指针</span></span><br><span class="line">		x-&gt;NoBarrier_SetNext(i, prev[i]-&gt;NoBarrier_Next(i));</span><br><span class="line">		<span class="comment">// 内部会强制进行同步</span></span><br><span class="line">		prev[i]-&gt;SetNext(i, x);</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>跳表实现的难点在于层数的确定，而LevelDB的难点在于<strong>插入节点如何保证并发写入的时候能够正确的并发读</strong>。</p>
<p><strong>RandomHeight() 新增层级选举</strong>：</p>
<p>在LevelDb中层级选举的核心的代码是：<code>height &lt; kMaxHeight &amp;&amp; rnd_.OneIn(kBranching)</code>，内部在控制跳表层数最多不超过<code>kMaxHeight</code>层的情况下，对于4取余的操作实现<strong>构造 P = 3/4 的几何分布</strong>，最终判断是否新增层数。</p>
<blockquote>
<p>原始情况下跳表增加1层为 1/2，2层为1/4，3层为1/8，4层为1/16。LevelDB的11层最高层限制key的数量，但是11层的节点概率通常会非常非常小。<br>最终LevelDB选择的结果是3/4 的节点为 1 层节点，3/16 的节点为 2 层节点，3/64 的节点为 3 层节点，依此类推。</p>
</blockquote>
<p>层级选举的特点：</p>
<ol>
<li>插入新节点的指针数通过独立计算一个概率值决定，使全局节点的指针数满足几何分布即可。</li>
<li>插入时不需要做额外的节点调整，只需要先找到其需要放的位置，然后修改他和前驱的指向即可。</li>
</ol>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> Key, <span class="class"><span class="keyword">class</span> <span class="title">Comparator</span>&gt;</span></span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="title">int</span> <span class="title">SkipList</span>&lt;Key, Comparator&gt;:</span>:RandomHeight() &#123;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 在kBranching中以1的概率增加高度</span></span><br><span class="line">	</span><br><span class="line">	<span class="keyword">static</span> <span class="keyword">const</span> <span class="keyword">unsigned</span> <span class="keyword">int</span> kBranching = <span class="number">4</span>;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">int</span> height = <span class="number">1</span>;</span><br><span class="line">	<span class="comment">// rnd_.OneIn(kBranching):"1/n "的时间会返回真没其他情况会返回假</span></span><br><span class="line">	<span class="comment">// 相当于层数会按照4 的倍数减小， 4层是3层的4分之一，简单理解为 每次加一层概率就要乘一个 1/4。</span></span><br><span class="line">	<span class="keyword">while</span> (height &lt; kMaxHeight &amp;&amp; rnd_.OneIn(kBranching)) &#123;</span><br><span class="line">	</span><br><span class="line">		height++;</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	assert(height &gt; <span class="number">0</span>);</span><br><span class="line">	</span><br><span class="line">	assert(height &lt;= kMaxHeight);</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">return</span> height;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>从上面的代码可以看到概率P使用了1/4计算方式，使用1/4的好处是让层数更为分散，典型的时间换空间的操作，虽然会牺牲一部分空间，但是获得更高的性能，<strong>在此情况下，可以最多支持 n = (1/p)^kMaxHeight 个节点的情况</strong>。</p>
<blockquote>
<p>对于LevelDB这种写快过读的业务，效率是最优考虑。</p>
</blockquote>
<p>12层高的节点最多可以存储多少数据？那么可以直接使用4^12 计算约等于 <strong>16M</strong>。当然12层的概率微乎其微。</p>
<h2 id="删除操作"><a href="#删除操作" class="headerlink" title="删除操作"></a>删除操作</h2><p>LevelDB跳表是没有删除这个概念的，相对应的更新也是针对next指针的变动。</p>
<ol>
<li>除非跳表被销毁，跳表节点<strong>只会增加而不会被删除</strong>，因为跳表<strong>根本不对外提供删除接口</strong>。</li>
<li>被插入到跳表中的节点，除了 next 指针其他域都是不可变的，并且只有插入操作会改变跳表。（以此来替代更新）</li>
</ol>
<h2 id="遍历操作"><a href="#遍历操作" class="headerlink" title="遍历操作"></a>遍历操作</h2><p>之前的[[LSM-Tree - LevelDb 源码解析]] 分析解释过整个跳表的遍历通过<code>Iterator</code>完成，内部使用了归并排序对于key进行排序，同时<code>null ptr</code>作为特殊值永远排在最前面。</p>
<p>LevelDB自带的迭代器实现较为丰富，除开迭代器经典的<code>remove()</code>，<code>next()</code>、<code>haseNext()</code>之外，还有<code>Seek</code>，<code>SeekToFirst</code>，<code>SeekToLast</code>、以及<code>Prev</code>向前遍历的操作</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// Advances to the next position.</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// REQUIRES: Valid()</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Next</span><span class="params">()</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">// Advances to the previous position.</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// REQUIRES: Valid()</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Prev</span><span class="params">()</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">// Advance to the first entry with a key &gt;= target</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Seek</span><span class="params">(<span class="keyword">const</span> Key&amp; target)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">// Position at the first entry in list.</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// Final state of iterator is Valid() iff list is not empty.</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">SeekToFirst</span><span class="params">()</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">// Position at the last entry in list.</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// Final state of iterator is Valid() iff list is not empty.</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">SeekToLast</span><span class="params">()</span></span>;</span><br></pre></td></tr></table></figure>

<p>这里需要特意强调的是向前遍历这个操作<strong>并不是通过增加prev指针反向迭代</strong>的，而是<strong>从head开始查找</strong>，也是时间换空间。</p>
<p>最后有两个比较频繁的使用操作<code>FindLast</code>和<code>FindLessThan</code>，注释写的简单明了，就不多介绍了。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// Return the latest node with a key &lt; key.</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// Return head_ if there is no such node.</span></span><br><span class="line"></span><br><span class="line"><span class="function">Node* <span class="title">FindLessThan</span><span class="params">(<span class="keyword">const</span> Key&amp; key)</span> <span class="keyword">const</span></span>;</span><br><span class="line"></span><br><span class="line">  </span><br><span class="line"><span class="comment">// Return the last node in the list.</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// Return head_ if list is empty.</span></span><br><span class="line"></span><br><span class="line"><span class="function">Node* <span class="title">FindLast</span><span class="params">()</span> <span class="keyword">const</span></span>;</span><br></pre></td></tr></table></figure>

<h1 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h1><p>LevelDB的跳表设计难点主要体现在并发读写的维持以及节点的层级选举上面，这一部分是和原始的跳表差别比较大的地方，而其他地方基本可以看作原始跳表的理论设计的，所以把 LevelDB 作为跳表的模板代码学习也是十分推荐的。</p>
<h1 id="参考资料"><a href="#参考资料" class="headerlink" title="参考资料"></a>参考资料</h1><p><span class="exturl" data-url="aHR0cHM6Ly93d3cuamlhbnNodS5jb20vcC85ZDgyOTY1NjI4MDY=" title="https://www.jianshu.com/p/9d8296562806">Skip List–跳表（全网最详细的跳表文章没有之一） - 简书 (jianshu.com)<i class="fa fa-external-link"></i></span></p>
<p>跳表数据结构的实现，JAVA版本的链表可以看下面的代码：<br><span class="exturl" data-url="aHR0cHM6Ly9naXRodWIuY29tL3dhbmd6aGVuZzA4MjIvYWxnby9ibG9iL21hc3Rlci9qYXZhLzE3X3NraXBsaXN0L1NraXBMaXN0LmphdmE=" title="https://github.com/wangzheng0822/algo/blob/master/java/17_skiplist/SkipList.java">algo/SkipList.java at master · wangzheng0822/algo · GitHub<i class="fa fa-external-link"></i></span></p>
<h1 id="相关阅读"><a href="#相关阅读" class="headerlink" title="相关阅读"></a>相关阅读</h1><p><span class="exturl" data-url="aHR0cHM6Ly9zZWdtZW50ZmF1bHQuY29tL2EvMTE5MDAwMDA0MTY1MjAwMw==" title="https://segmentfault.com/a/1190000041652003">[《数据密集型型系统设计》LSM-Tree VS BTree]<i class="fa fa-external-link"></i></span></p>
<p><span class="exturl" data-url="aHR0cHM6Ly9zZWdtZW50ZmF1bHQuY29tL2EvMTE5MDAwMDA0MTcyMDIwNQ==" title="https://segmentfault.com/a/1190000041720205">[LSM-Tree - LevelDb了解和实现]<i class="fa fa-external-link"></i></span></p>
<p><span class="exturl" data-url="aHR0cHM6Ly9zZWdtZW50ZmF1bHQuY29tL2EvMTE5MDAwMDA0MTg2NDU3OQ==" title="https://segmentfault.com/a/1190000041864579">[LSM-Tree - LevelDb 源码解析]<i class="fa fa-external-link"></i></span></p>
<p><span class="exturl" data-url="aHR0cHM6Ly9zZWdtZW50ZmF1bHQuY29tL2EvMTE5MDAwMDA0MTg2OTU4Ng==" title="https://segmentfault.com/a/1190000041869586">[LSM-Tree - LevelDb Skiplist跳表]<i class="fa fa-external-link"></i></span></p>
<p><span class="exturl" data-url="aHR0cHM6Ly9zZWdtZW50ZmF1bHQuY29tL2EvMTE5MDAwMDA0MTg3MzQwMA==" title="https://segmentfault.com/a/1190000041873400">[LSM-Tree - LevelDb 布隆过滤器]<i class="fa fa-external-link"></i></span></p>
<script type="text/javascript" src="https://cdn.jsdelivr.net/npm/kity@2.0.4/dist/kity.min.js"></script><script type="text/javascript" src="https://cdn.jsdelivr.net/npm/kityminder-core@1.4.50/dist/kityminder.core.min.js"></script><script defer="true" type="text/javascript" src="https://cdn.jsdelivr.net/npm/hexo-simple-mindmap@0.2.0/dist/mindmap.min.js"></script><link rel="stylesheet" type="text/css" href="https://cdn.jsdelivr.net/npm/hexo-simple-mindmap@0.2.0/dist/mindmap.min.css">
    </div>

    
    
    
        

<div>
<ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者： </strong>阿东
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="https://whitestore.top/2022/05/21/level-skiplist/" title="LSM-Tree - LevelDb Skiplist跳表">https://whitestore.top/2022/05/21/level-skiplist/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <span class="exturl" data-url="aHR0cHM6Ly9jcmVhdGl2ZWNvbW1vbnMub3JnL2xpY2Vuc2VzL2J5LW5jLzQuMC96aC1DTg=="><i class="fa fa-fw fa-creative-commons"></i>BY-NC</span> 许可协议。转载请注明出处！
  </li>
</ul>
</div>


      <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/LevelDB/" rel="tag"># LevelDB</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/2022/05/21/leveled-bloom/" rel="prev" title="LSM-Tree - LevelDb 布隆过滤器">
      <i class="fa fa-chevron-left"></i> LSM-Tree - LevelDb 布隆过滤器
    </a></div>
      <div class="post-nav-item">
    <a href="/2022/05/21/leveldb-source/" rel="next" title="LSM-Tree - LevelDb 源码解析">
      LSM-Tree - LevelDb 源码解析 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          
    <div class="comments" id="valine-comments"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#LSM-Tree-LevelDb-Skiplist跳表"><span class="nav-number">1.</span> <span class="nav-text">LSM-Tree - LevelDb Skiplist跳表</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#跳表介绍"><span class="nav-number">2.</span> <span class="nav-text">跳表介绍</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#背景"><span class="nav-number">2.1.</span> <span class="nav-text">背景</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#实现"><span class="nav-number">2.2.</span> <span class="nav-text">实现</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#查询"><span class="nav-number">2.3.</span> <span class="nav-text">查询</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#插入"><span class="nav-number">2.4.</span> <span class="nav-text">插入</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#删除"><span class="nav-number">2.5.</span> <span class="nav-text">删除</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#使用场景"><span class="nav-number">2.6.</span> <span class="nav-text">使用场景</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#LevelDb跳表实现"><span class="nav-number">3.</span> <span class="nav-text">LevelDb跳表实现</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#基础结构"><span class="nav-number">3.1.</span> <span class="nav-text">基础结构</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#重要方法"><span class="nav-number">3.2.</span> <span class="nav-text">重要方法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#查询操作"><span class="nav-number">3.3.</span> <span class="nav-text">查询操作</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#插入操作"><span class="nav-number">3.4.</span> <span class="nav-text">插入操作</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#删除操作"><span class="nav-number">3.5.</span> <span class="nav-text">删除操作</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#遍历操作"><span class="nav-number">3.6.</span> <span class="nav-text">遍历操作</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#总结"><span class="nav-number">4.</span> <span class="nav-text">总结</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#参考资料"><span class="nav-number">5.</span> <span class="nav-text">参考资料</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#相关阅读"><span class="nav-number">6.</span> <span class="nav-text">相关阅读</span></a></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">阿东</p>
  <div class="site-description" itemprop="description">随遇而安</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">239</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">36</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">37</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <span class="exturl" data-url="aHR0cHM6Ly9naXRodWIuY29tL2xhenlUaW1lcw==" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;lazyTimes"><i class="fa fa-fw fa-github"></i>GitHub</span>
      </span>
      <span class="links-of-author-item">
        <span class="exturl" data-url="bWFpbHRvOjEwOTc0ODM1MDhAcXEuY29t" title="E-Mail → mailto:1097483508@qq.com"><i class="fa fa-fw fa-envelope"></i>E-Mail</span>
      </span>
  </div>


  <div class="links-of-blogroll motion-element">
    <div class="links-of-blogroll-title">
      <i class="fa fa-fw fa-link"></i>
      友情链接
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-item">
          <span class="exturl" data-url="aHR0cHM6Ly93d3cuNTJwb2ppZS5jbi9ob21lLnBocD9tb2Q9c3BhY2UmdWlkPTE0OTc3MTgmZG89dGhyZWFkJnZpZXc9bWUmZnJvbT1zcGFjZQ==" title="https:&#x2F;&#x2F;www.52pojie.cn&#x2F;home.php?mod&#x3D;space&amp;uid&#x3D;1497718&amp;do&#x3D;thread&amp;view&#x3D;me&amp;from&#x3D;space">吾爱破解</span>
        </li>
        <li class="links-of-blogroll-item">
          <span class="exturl" data-url="aHR0cHM6Ly9qdWVqaW4uaW0vdXNlci8yOTk5MTIzNDUyNjI2MzY2" title="https:&#x2F;&#x2F;juejin.im&#x2F;user&#x2F;2999123452626366">掘金</span>
        </li>
        <li class="links-of-blogroll-item">
          <span class="exturl" data-url="aHR0cHM6Ly9zZWdtZW50ZmF1bHQuY29tL3UvbGF6eXRpbWVz" title="https:&#x2F;&#x2F;segmentfault.com&#x2F;u&#x2F;lazytimes">思否</span>
        </li>
    </ul>
  </div>

      </div>

      <div class="wechat_OA">
        <span>欢迎关注我的公众号</span>
        <br>
          <!-- 这里添加你的二维码图片 -->
        <img src ="https://adong-picture.oss-cn-shenzhen.aliyuncs.com/adong/wechat_channel.jpg">
      </div>
        <div class="back-to-top motion-element">
          <i class="fa fa-arrow-up"></i>
          <span>0%</span>
        </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2023</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">阿东</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-area-chart"></i>
    </span>
      <span class="post-meta-item-text">站点总字数：</span>
    <span title="站点总字数">2m</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
      <span class="post-meta-item-text">站点阅读时长 &asymp;</span>
    <span title="站点阅读时长">29:50</span>
</div>
  <div class="powered-by">由 <span class="exturl theme-link" data-url="aHR0cHM6Ly9oZXhvLmlv">Hexo</span> & <span class="exturl theme-link" data-url="aHR0cHM6Ly90aGVtZS1uZXh0Lm9yZw==">NexT.Gemini</span> 强力驱动
  </div>

        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/jquery@3/dist/jquery.min.js"></script>
  <script src="//cdn.jsdelivr.net/gh/fancyapps/fancybox@3/dist/jquery.fancybox.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>




  




  
<script src="/js/local-search.js"></script>













  

  


<script>
NexT.utils.loadComments(document.querySelector('#valine-comments'), () => {
  NexT.utils.getScript('//unpkg.com/valine/dist/Valine.min.js', () => {
    var GUEST = ['nick', 'mail', 'link'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(item => {
      return GUEST.includes(item);
    });
    new Valine({
      el         : '#valine-comments',
      verify     : false,
      notify     : true,
      appId      : 'qMUpEEvBgXaMDD1b0ftgi9xr-gzGzoHsz',
      appKey     : 'UCdfT4Rfih6MO6y8DI4fstf6',
      placeholder: "Just go go",
      avatar     : 'mm',
      meta       : guest,
      pageSize   : '10' || 10,
      visitor    : false,
      lang       : 'zh-CN' || 'zh-cn',
      path       : location.pathname,
      recordIP   : false,
      serverURLs : ''
    });
  }, window.Valine);
});
</script>

</body>
</html>
